Search results for "Graph traversal"
showing 3 items of 3 documents
Curve Extraction by Geodesics Fusion: Application to Polymer Reptation Analysis
2016
© Springer International Publishing Switzerland 2016. In the molecular field, researchers analyze dynamics of polymers by microscopy: several measurements such as length and curvature are performed in their studies. To achieve correct analysis they need to extract the curve representing as good as possible the observed polymer shape which is a grayscale thick curve with noise and blur. We propose, in this paper, a method to extract such a curve. A polymer chain moves in a snake-like fashion (Reptation): it can self-intersect and form several complex geometries. To efficiently extract the different geometries, we generate the curve by computing a piecewise centerline browsing the shape by ge…
The mixed general routing polyhedron
2003
[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the…
Efficient evaluation for a subset of recursive queries
1991
Abstract We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluat…